//
//  BinaryTree.m
//  Objc进阶Demo
//
//  Created by Don't update on 2018/8/20.
//  Copyright © 2018年 Don't update. All rights reserved.
//

#import "BinaryTree.h"

@implementation BinaryTree

+(BinaryTree *)createTreeWithValues:(NSArray *)arr{
    BinaryTree *root = nil;
    for (NSInteger i = 0; i<arr.count; i++) {
       root = [BinaryTree addTreeNode:root WithValue:[arr[i] integerValue]];
    }
    return root;
}


+(BinaryTree *)addTreeNode:(BinaryTree *)treeNode WithValue:(NSInteger)value{
    if (!treeNode) {
        treeNode = [BinaryTree new];
        treeNode.Value = value;
    }
    else if(treeNode.Value<value){
       treeNode.rightNode = [BinaryTree addTreeNode:treeNode.rightNode WithValue:value];
    }
    else if(treeNode.Value>=value){
       treeNode.leftNode = [BinaryTree addTreeNode:treeNode.leftNode WithValue:value];
    }
    return treeNode;
}




+(BinaryTree *)treeNodeAtIndex:(NSInteger)index inTree:(BinaryTree *)rootNode{
    //按层次遍历
    if(!rootNode||index<0){
        return nil;
    }
    NSMutableArray *queueArray = [NSMutableArray array];//数组当成队列
    [queueArray addObject:rootNode];//压入根节点
    NSLog(@"%lu",rootNode.Value);
    while (queueArray.count>0) {
        BinaryTree *node = [queueArray firstObject];
        if (index == 0) {
            return  node;
        }
        [queueArray removeObjectAtIndex:0];//弹出最上边的节点,仿照队列先进先出原则
        index--;
        
        if(node.leftNode){
            NSLog(@"%lu",node.leftNode.Value);
            [queueArray addObject:node.leftNode];//压入左节点
        }
        if(node.rightNode){
            NSLog(@"%lu",node.rightNode.Value);
            [queueArray addObject:node.rightNode];
        }
    }
    return  nil;
}

//先序遍历
+(void)perOrderTraverseTree:(BinaryTree *)rootNode handler:(void (^)(BinaryTree *))handler{
    if(rootNode){
        if (handler) {
            handler(rootNode);
        }
        [self perOrderTraverseTree:rootNode.leftNode handler:handler];
        [self perOrderTraverseTree:rootNode.rightNode handler:handler];
    }
}


//中序遍历
+(void)inOrderTraverseTree:(BinaryTree *)rootNode handler:(void (^)(BinaryTree *))handler{
    if (rootNode) {
        [self inOrderTraverseTree:rootNode.leftNode handler:handler];
        if (handler) {
            handler(rootNode);
        }
        [self inOrderTraverseTree:rootNode.rightNode handler:handler];
    }
}

//后序遍历
+(void)postOrderTraverseTree:(BinaryTree *)rootNode handler:(void (^)(BinaryTree *))handler{
    if (rootNode) {
        [self postOrderTraverseTree:rootNode.leftNode handler:handler];
        [self postOrderTraverseTree:rootNode.rightNode handler:handler];
        
        if (handler) {
            handler(rootNode);
        }
    }
}

//层次遍历(广度优先)
+(void)leveTraverseTree:(BinaryTree *)rootNode handler:(void (^)(BinaryTree *))handler{
    if(!rootNode){
        return;
    }
    NSMutableArray *queueArray = [NSMutableArray array];
    [queueArray addObject:rootNode];
    while (queueArray.count>0) {
        BinaryTree *node = [queueArray firstObject];
        
        if (handler) {
            handler(node);
        }
        [queueArray removeObjectAtIndex:0];
        if (node.leftNode) {
            [queueArray addObject:node.leftNode];
        }
        if (node.rightNode) {
            [queueArray addObject:node.rightNode];
        }
    }
}

+(NSInteger)depthOfTree:(BinaryTree *)rootNode{
    if (!rootNode) {
        return 0;
    }
    if (!rootNode.leftNode && rootNode.rightNode) {
        return 1;
    }
    
    NSInteger leftDepth = [self depthOfTree:rootNode.leftNode];
    NSInteger rightDepth = [self depthOfTree:rootNode.rightNode];
    return  MAX(leftDepth, rightDepth)+1;
}


+(NSInteger)widthOfTree:(BinaryTree *)rootNode{
    if(!rootNode){
        return 0;
    }
    NSMutableArray *queueArray = [NSMutableArray array];
    [queueArray addObject:rootNode];
    NSInteger maxWidth = 1;
    NSInteger curWidth = 0;
    
    while (queueArray.count >0) {
        curWidth = queueArray.count;
        for (NSInteger i = 0; i<curWidth; i++) {
            BinaryTree *node = [queueArray firstObject];
            [queueArray removeObjectAtIndex:0];
            if (node.leftNode) {
                [queueArray addObject:node.leftNode];
            }
            if (node.rightNode) {
                [queueArray addObject:node.rightNode];
            }
         
        }
           maxWidth = MAX(maxWidth, queueArray.count);
    }
    return maxWidth;
}


+(NSInteger)numberOfNodexInTree:(BinaryTree *)rootNode{
    if (!rootNode) {
        return 0;
    }
    //节点数=左子树节点数-右子树节点数-1 (根节点)
    return [self numberOfNodexInTree:rootNode]+[self numberOfNodexInTree:rootNode.rightNode]+1;
}

@end
